﻿//【案例开放039】0618上机编程“基站信号地图”学习交流
//日期：2021-06-25 15:29浏览：17837回复：502026-07-02 失效
// 1. 题目
//今天学习0618工作级第三题、专业级第一题。题目：
//题目描述
//视一片区域为一个 rows * cols 的矩阵（行列编号皆从 1
//开始），初始有一批基站分布在某些单元格内（位置无重复）。现对这片区域进行改造，涉及两种操作：
//?
// add：在单元格[row,col]中添加一个基站，若该单元格已经存在基站，则不做任何动作。
//?
// delete：清除单元格[row,col]及周边范围（上、下、左、右、对角的相邻单元格）中的基站。
//假设每个基站的信号覆盖范围为上、下、左、右、对角的相邻单元格；每存在一个基站，覆盖范围内的每个单元格的信号强度增加
// 1 。 改造完成后，请统计最终矩阵各单元格（不含基站位置）的信号强度之和。 输入
// l首行两个整数rows cols，表示矩阵的行数和列数，取值范围均为[1,100]。
// l第二行是一个整数 baseStationCnt，表示初始基站的个数，取值范围[0,100];
//接下来 baseStationCnt 行，每行输入一个基站的位置，格式为row col，row的取值范围
//[1,rows]，col的取值范围 [1,cols]；输入保证初始基站位置无重复。
// l然后一行是一个整数 cmdCnt，表示改造操作的个数，取值范围：[0,100]。
//接下来 cmdCnt 行，每行一个操作，格式为操作 row col，操作仅为add或delete,
// row的取值范围 [1,rows]，col的取值范围 [1,cols]。 输出
//一个整数，表示最终矩阵各单元格（不含基站位置）的信号强度之和。
//样例
//输入样例 1
// 4 6
// 3
// 2 2
// 3 3
// 4 4
// 3
// delete 4 3
// add 1 2
// delete 2 5
//输出样例 1
// 11
//提示样例 1
//如下图所示：
// https://oj.rnd.huawei.com/public/upload/63935ea7f6.png
//左边矩阵表示初始基站的分布（*表示基站）
// delete 4 3 操作：清除单元格[4,3]周边范围内的两个基站
// add 1 2 操作：在单元格[1,2]中添加基站
// delete 2 5
// 操作：单元格[2,5]周边范围内没有基站，因此该操作不改变矩阵内的基站。
//最后存在2个基站，如右边矩阵所示：绿框表示基站[1,2]的信号覆盖范围，蓝框表示基站[2,2]的信号覆盖范围。
//最终矩阵每个单元格（不含基站位置）的信号强度为图中数字，和为11。 输入样例 2 1
// 1
// 0
// 0
//输出样例 2
// 0
// 2. 题目分析
//题目理解：
// Windows上有个小游戏：扫雷，如下图所示：格子中的数字表示周围一圈的地雷个数
//此题中矩阵区域各个单元格的信号强度和扫雷游戏中地雷个数是类似的概念。
//对基站区域进行改造有两种操作：
//?
// add：在单元格[row,col]中添加一个基站，题目说了：若该单元格已经存在基站，则不做任何动作。
//?
// delete：清除单元格[row,col]及周边范围（上、下、左、右、对角的相邻单元格）中的基站。注意要清除指定单元格、再加上周围一圈（共9个单元格）的所有基站，不要把[row,col]位置的基站漏了。
//计算信号强度时，基站本身是不参与计算的，题目有说明：请统计最终矩阵各单元格（不含基站位置）的信号强度之和。
//解题思路：
//有两种思路：
// l先通过增删基站，记录下基站的位置；最后再计算每一个单元格的信号强度并累加。【推荐】
// l依次处理每一个增、删基站的命令，动态计算每一个单元格的信号强度；最后一次累加各单元格信号强度；这种做法比较麻烦，代码量会比较多。
//基站A周围的九宫格如下图所示：
//有两个地方需要遍历单元格及其周围的九宫格：
// ldelete命令清除单元格[row,col]及周边范围基站
// l统计每个基站的信号覆盖
//遍历方法通常有两种：
// l用两层for循环
//优点：更通用的做法，例如当题目改为遍历超过9个单元格的时候，只需要改动少许代码
//缺点：可能会增加圈复杂度和代码嵌套深度，注意拆分函数
// l不用循环，直接用相对偏移操作上、下、左、右、对角的相邻单元格，例如左上角是matrix[row
// - 1][col - 1]、右下角是matrix[row + 1][col + 1]
//优点：圈复杂度和代码嵌套深度会比较低
//缺点：当需求变化，例如遍历超过9个单元格的时候，会写较多的代码
#include <stdbool.h>
#include <stdio.h>

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define DEBUG
#ifdef DEBUG
#define PF(...) printf(__VA_ARGS__)
#else
#define PF(...)
#endif

#define MAX_BASESTATION_CNT 100
#define MAX_N_CMD 100
#define MAX_CMD_BUF_LEN 16
typedef struct {
  int row;
  int col;
} Coord;
typedef struct {
  char cmd[MAX_CMD_BUF_LEN];
  Coord coord;
} Command;
// 该解法用一个二维数组int
// a[102][102]表示矩阵，每个元素的值：0表示没有基站、1表示有基站。 1)
// 添加基站时，通过设置 a[commands[i].coord.row][commands[i].coord.col] = 1; 2)
// 清除基站时，遍历单元格[row,col]周围九宫格（含自身），不管是否存在基站、都置为0。
// 3)
// 最后计算信号强度时，把每个单元格上下左右斜角8个单元格的值累加，即为该单元格的信号强度。
// 遍历方法：没有用循环、而是采用相对偏移的方法；当处理的单元格数量不大时，这样处理比较好，可以避免写多层for循环。
// 由于题目给的行和列都是从下标1开始，所以最后遍历矩阵时，是从1开始。
// 定义数组时，范围为[row + 2][col +
// 2]，这是一种常见的防止数组越界的技巧，如果不加2的话就需要额外加一些判断条件。
// 思路清晰、代码简洁。
// 待实现函数，在此函数中填入答题代码
int GetMatrixSum(int rows, int cols, const Coord *baseStations,
                 int baseStationCnt, const Command *commands, int cmdCnt) {
  int a[MAX_BASESTATION_CNT + 2][MAX_BASESTATION_CNT + 2] = {0};
  int sum = 0;
  for (int i = 0; i < baseStationCnt; i++) {
    a[baseStations[i].row][baseStations[i].col] = 1;
  }
  for (int i = 0; i < cmdCnt; i++) {
    if (commands[i].cmd[0] == 'd') {
      a[commands[i].coord.row][commands[i].coord.col + 1] = 0;
      a[commands[i].coord.row][commands[i].coord.col] = 0;
      a[commands[i].coord.row][commands[i].coord.col - 1] = 0;
      a[commands[i].coord.row - 1][commands[i].coord.col + 1] = 0;
      a[commands[i].coord.row - 1][commands[i].coord.col] = 0;
      a[commands[i].coord.row - 1][commands[i].coord.col - 1] = 0;
      a[commands[i].coord.row + 1][commands[i].coord.col + 1] = 0;
      a[commands[i].coord.row + 1][commands[i].coord.col] = 0;
      a[commands[i].coord.row + 1][commands[i].coord.col - 1] = 0;
    } else {
      a[commands[i].coord.row][commands[i].coord.col] = 1;
    }
  }
  for (int i = 1; i <= rows; i++) {
    for (int j = 1; j <= cols; j++) {
      if (a[i][j] == 0) {
        sum = sum + a[i - 1][j - 1] + a[i + 1][j + 1] + a[i - 1][j + 1] +
              a[i + 1][j - 1] + a[i][j - 1] + a[i + 1][j] + a[i][j + 1] +
              a[i - 1][j];
      }
    }
  }
  return sum;
}
int main(void) {
  int rows, cols, baseStationCnt;
  if (scanf("%d%d%d", &rows, &cols, &baseStationCnt) != 3) {
    return -1;
  }
  Coord baseStations[MAX_BASESTATION_CNT];
  for (int i = 0; i < baseStationCnt; i++) {
    if (scanf("%d%d", &baseStations[i].row, &baseStations[i].col) != 2) {
      return -1;
    }
  }
  int cmdCnt;
  if (scanf("%d", &cmdCnt) != 1) {
    return -1;
  }
  Command commands[MAX_N_CMD];
  for (int i = 0; i < cmdCnt; i++) {
    if (scanf("%s %d %d", commands[i].cmd, sizeof(commands[i].cmd),
              &commands[i].coord.row, &commands[i].coord.col) != 3) {
      return -1;
    }
  }
  int total =
      GetMatrixSum(rows, cols, baseStations, baseStationCnt, commands, cmdCnt);
  printf("%d", total);
  return 0;
}

// import java.nio.charset.StandardCharsets;
// import java.util.Scanner;
// public class Main {
// static class Command {
// private final String cmd;
// private final int row;
// private final int col;
// Command(String inputStr) {
// String[] inputArray = inputStr.split(" ");
// this.cmd = inputArray[0];
// this.row = Integer.parseInt(inputArray[1]);
// this.col = Integer.parseInt(inputArray[2]);
//}
//}
//// 待实现函数，在此函数中填入答题代码
// private static int getMatrixSum(int rows, int cols, int[][] baseStations,
// Command[] commands) { int[][] arr = new int[rows][cols]; for (int i = 0; i <
// baseStations.length; i++) { arr[baseStations[i][0] - 1][baseStations[i][1] -
// 1] = 1;
//}
// for (int j = 0; j < commands.length; j++) {
// if (commands[j].cmd.equals("add")) {
// arr[commands[j].row - 1][commands[j].col - 1] = 1;
//} else if (commands[j].cmd.equals("delete")) {
// int x = commands[j].row - 1;
// int y = commands[j].col - 1;
// arr[x][y] = 0;
// for (int m = Math.max(0, x - 1); m <= Math.min(rows - 1, x + 1); m++) {
// for (int n = Math.max(0, y - 1); n <= Math.min(cols - 1, y + 1); n++) {
// arr[m][n] = 0;
//}
//}
//}
//}
// int res = 0;
// for (int i = 0; i < arr.length; i++) {
// for (int j = 0; j < arr[i].length; j++) {
// if (arr[i][j] == 1) {
// for (int i1 = Math.max(0, i - 1); i1 <= Math.min(rows - 1, i + 1); i1++) {
// for (int j1 = Math.max(0, j - 1); j1 <= Math.min(cols - 1, j + 1); j1++) {
// if (arr[i1][j1] == 0) {
// res++;
//}
//}
//}
//}
//}
//}
// return res;
//}
///**
// * main入口由OJ平台调用
// */
// public static void main(String[] args) {
// Scanner cin = new Scanner(System.in, StandardCharsets.UTF_8.name());
// int rows = cin.nextInt();
// int cols = cin.nextInt();
// cin.nextLine();
// int baseStationCnt = Integer.parseInt(cin.nextLine());
// int[][] baseStations = new int[baseStationCnt][2];
// for (int i = 0; i < baseStationCnt; i++) {
// String[] line = cin.nextLine().split(" ");
// baseStations[i][0] = Integer.parseInt(line[0]);
// baseStations[i][1] = Integer.parseInt(line[1]);
//}
// int cmdCnt = Integer.parseInt(cin.nextLine());
// Command[] commands = new Command[cmdCnt];
// for (int i = 0; i < cmdCnt; i++) {
// commands[i] = new Command(cin.nextLine());
//}
// cin.close();
// int result = getMatrixSum(rows, cols, baseStations, commands);
// System.out.println(result);
//}
//}

//该解法用一个二维数组表示矩阵，每个元素的值：0表示没有基站、1表示有基站。
//清除基站时，遍历单元格[row,col]周围九宫格（含自身），不管是否存在基站、都置为0。
//和上面C语言代码不同之处：该解法用两层for循环来遍历九宫格。
//除了嵌套深度比较大外，代码逻辑还是很清晰、代码量也不大。
//待改进之处：
// l圈复杂度13比较大，会扣3分
// l最大深度7已经濒临边界，如果大于等于8将会扣分为0；可以参考上面C++的方法减少循环嵌套层次，或者抽取出函数。
//参见《上机编程认证科目CleanCode判分规则2.0》http://3ms.huawei.com/km/groups/3803117/blogs/details/8722089?l=zh-cn
// 6. 员工4-PYTHON代码：17行、最大圈复杂度7
// from typing import List
// import numpy as np
// class Solution:
// def get_matrix_sum(self, rows: int, cols: int, base_stations:
// List[List[int]], commands: List[tuple]) -> int:
//"""
//在此添加你的代码
//"""
// matrix = np.zeros((rows+2, cols+2))
// for corr in base_stations:
// matrix[corr[0], corr[1]] = -10000
// for com in commands:
// if com[0] == 'delete':
// matrix[com[1][0]-1: com[1][0]+2, com[1][1]-1: com[1][1]+2] = np.zeros((3, 3))
// elif com[0] == 'add':
// matrix[com[1][0], com[1][1]] = -10000
// corrs = np.where(matrix == -10000)
// for i in range(len(corrs[0])):
// matrix[corrs[0][i]-1: corrs[0][i]+2, corrs[1][i]-1: corrs[1][i]+2] +=
// np.ones((3, 3)) corrs = np.where(matrix < 0) for i in range(len(corrs[0])):
// matrix[corrs[0][i], corrs[1][i]] = 0
// matrix = matrix[1: -1, 1: -1]
// return int(np.sum(matrix))
// if __name__ == "__main__":
// rows, cols = list(map(int, input().strip().split(' ')))
// base_station_cnt = int(input().strip())
// base_stations = [list(map(int, input().strip().split())) for _ in
// range(base_station_cnt)] cmd_cnt = int(input().strip()) commands = [] for _
// in range(cmd_cnt): cmd_ = input().strip().split(' ')
// commands.append((cmd_[0], [int(cmd_[1]), int(cmd_[2])])) function =
// Solution() results = function.get_matrix_sum(rows, cols, base_stations,
// commands) print(results)
//该解法用的是numpy库的二维数组。
//每个数组元素的值：0表示没有基站、-10000表示有基站。
// 1)删除基站时，直接用np.zeros((3, 3))将对应单元格周围九宫格全部初始化为0
// 2)计算信号强度时，corrs = np.where(matrix == -10000)将所有基站位置筛选出来。
// 3)np.ones((3, 3))创建一个3*3的矩阵，每个矩阵元素以 1 来填充。
// 4)将基站位置对应的矩阵值置为0后，np.sum统计的结果就是信号强度之和。
//该解法利用了python的扩展库numpy的功能，用较少的代码就正确实现了功能。
//我们在熟练掌握一种语言及其标准库外，还应该学习常用的扩展库，可以事半功倍。
// NumPy(Numerical Python) 是 Python
// 语言的一个扩展程序库，支持大量的维度数组与矩阵运算，此外也针对数组运算提供大量的数学函数库。
//参考NumPy 教程：https://www.runoob.com/numpy/numpy-tutorial.html
